from collections import defaultdict, deque
import sys
import threading
def main():
n, k = list(map(int, input().split()))
graph = defaultdict(list)
for _ in range(k):
a, b = list(map(int, input().split()))
a-=1
b-=1
graph[a].append(b)
graph[b].append(a)
def bipartite(colors):
for i in range(n):
if i not in colors and i in graph:
colors[i] = 0
stack = [i]
while stack:
cur = stack.pop()
for nei in graph[cur]:
if nei in colors:
if colors[nei]==colors[cur]: return False
else:
colors[nei] = colors[cur]^1
stack.append(nei)
return True
colors = {}
if bipartite(colors):
green = []
blue = []
for key in colors:
if colors[key] == 0:
green.append(key+1)
else:
blue.append(key+1)
print(len(green))
print(*green)
print(len(blue))
print(*blue)
else:
print("-1")
if __name__ == "__main__":
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)
thread = threading.Thread(target=main)
thread.start()
thread.join()
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T> using pbset=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
// template<class T> using pbmultiset=tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update> ;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vb = vector<bool>;
#define f(i,x,n) for(int i = x; i < n; i++)
#define rf(i,x,n) for(int i = x; i >= n; i--)
#define sz(a) int((a).size())
#define re return
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(x) (1LL*(x)*(x))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (1LL*(a/gcd(a,b))*b)
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define fi first
#define se second
#define CeilDiv(a,b) ((a+b-1)/b)
#define p_q priority_queue
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vector<ll>,greater<ll>>
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define gg cout<<-1<<endl
#ifndef ONLINE_JUDGE
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#include <debugging.h>
#else
#define dbg(v)
#endif
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> &v){for (auto& i : v) os << i << ' '; return os;}
#define tr(c, i) for (typeof (c).begin() i = c.begin(); i != c.end(); i++)
#define present(c, x) (c.find(x) != c.end())
#define cpresent(c, x) (find(all(c), x) != c.end())
///.........Bit_Manipulation...........///
#define MSB(mask) 63-__builtin_clzll(mask) /// 0 -> -1
#define LSB(mask) __builtin_ctzll(mask) /// 0 -> 64
#define SETBIT(mask) __builtin_popcountll(mask)
#define CHECKBIT(mask,bit) (mask&(1LL<<bit))
#define ONBIT(mask,bit) (mask|(1LL<<bit))
#define OFFBIT(mask,bit) (mask&~(1LL<<bit))
#define CHANGEBIT(mask,bit) (mask^(1LL<<bit))
const int inf = 2e9;
const ll mod = 1000000007;
// const ll mod = 998244353;
void solve(){
int n,m; cin >> n >> m;
vvi g(n);
f(i,0,m)
{
int u,v; cin >> u >> v;
u--,v--;
g[u].pb(v);
g[v].pb(u);
}
vi color(n),vis(n);
int c = 0, bp = 1;
vi part[2];
function<void(int,int)> dfs = [&](int i,int c){
vis[i] = 1;
color[i] = c;
part[c].pb(i+1);
for(auto v : g[i])
{
if(!vis[v])
dfs(v,c^1);
else if(color[i] == color[v])
bp = 0;
}
};
for(int i = 0 ; i < n; i++)
{
if(!vis[i]) dfs(i,0);
}
if(!bp) gg;
else
{
cout << sz(part[0]) << endl << part[0] << endl;
cout << sz(part[1]) << endl << part[1] << endl;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
signed t = 1;
// cin >> t;
while(t--) solve();
return 0;
}AND path in a binary tree | Factorial equations |
Removal of vertices | Happy segments |
Cyclic shifts | Zoos |
Build a graph | Almost correct bracket sequence |
Count of integers | Differences of the permutations |
Doctor's Secret | Back to School |
I am Easy | Teddy and Tweety |
Partitioning binary strings | Special sets |
Smallest chosen word | Going to office |
Color the boxes | Missing numbers |
Maximum sum | 13 Reasons Why |
Friend's Relationship | Health of a person |
Divisibility | A. Movement |
Numbers in a matrix | Sequences |
Split houses | Divisible |